#include "StdAfx.h"
#include "Sort.h"


Sort::Sort(void)
{
}


Sort::~Sort(void)
{
}

void Sort::swap(int& first,int& second){
	int temp = second;
	second = first;
	first = temp;
}

void Sort::SortEnter(){
	int numArray[] = {6,4,87,1,9,3,45,34};
	//Qsort(numArray,8,0,7);
	int* newArray = new int[8];
	MergeSort(numArray,8,newArray,0,7);

	for(int i = 0;i<8;i++){
		cout<<newArray[i]<<'\t';
	}
	cout<<endl;
}

void Sort::Qsort(int numArray[],int length,int begin,int end){
	if(numArray == NULL){
		return;
	}
	if(begin>end || end>=length){
		return;
	}
	int index = partition(numArray,length,begin,end);
	Qsort(numArray,length,begin,index-1);
	Qsort(numArray,length,index+1,end);

}

int Sort::partition(int numArray[],int length,int begin,int end){
	

	int middle = (begin+end)/2;

	swap(numArray[middle],numArray[end]);

	int small = begin-1;
	while(begin<end){
		if(numArray[begin]<numArray[end]){
			small++;
			if(small != begin){
				swap(numArray[small],numArray[begin]);
			}
		}
		begin++;
	}
	small++;
	swap(numArray[small],numArray[end]);
	return small;
}

void Sort::MergeSort(int numArray[],int length,int newArray[],int begin,int end){
	if(numArray == NULL || begin >=end){
		return;
	}
	int mid = (begin+end)/2;
	
	MergeSort(numArray,length,newArray,begin,mid);
	MergeSort(numArray,length,newArray,mid+1,end);
	MergeArray(numArray,length,begin,mid,end,newArray);
}

void Sort::MergeArray(int numArray[],int length,int begin,int mid,int end,int newArray[]){
	cout<<"begin="<<begin<<";mid="<<mid<<";end="<<end<<endl;
	int index = begin;
	int i = begin;
	int j = mid+1;
	while(i<=mid && j<=end){
		if(numArray[i]<numArray[j]){
			newArray[index] = numArray[i];
			i++;
		}else{
			newArray[index] = numArray[j];
			j++;
		}
		index++;
	}

	while(i<=mid){
		newArray[index]=numArray[i];
		i++;
		index++;
	}
	while(j<=end){
		newArray[index]=numArray[j];
		j++;
		index++;
	}

	for(int k = begin;k<=end;k++){
		numArray[k] = newArray[k];
	}
}